package offer;

public class UniquePath {
    public static void main(String[] args) {
        int num = 30;
        for (int i = 2; i <= num ; i++) {
            System.out.println("i:"+i+"\tj:"+i+"\t"+"paths:"+ uniquePaths(i,i));
        }
    }

    /*
        解题思路，要到达终点，必定要向左走m-1 次，向右走 n-1 次，共计走 m+n-2 次，对应二叉树向左向右，直到到达 m+n-2 层,时间复杂度 o(2^n)
     */
    public static int uniquePaths(int m,int n){
        return preOrderTraversal(0,0,m-1,n-1,m+n-2,0);
    }
    public static int preOrderTraversal(int curLeft,int curRight,int targetLeft,int targetRight,int targetHeight,int curHeight){
        if(curHeight == targetHeight){
            if(curLeft == targetLeft && curRight == targetRight){
                return 1;
            }else{
                return 0;
            }
        }else{
            int left = preOrderTraversal(curLeft+1,curRight,targetLeft,targetRight,targetHeight,curHeight+1);
            int right = preOrderTraversal(curLeft,curRight+1,targetLeft,targetRight,targetHeight,curHeight+1);
            return left+right;
        }
    }
}
